МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ "ЛЬВІВСЬКА ПОЛІТЕХНІКА"
ІТЕРАЦІЙНІ МЕТОДИ РОЗВ’ЯЗУВАННЯ СИСТЕМ
ЛІНІЙНИХ АЛГЕБРАЇЧНИХ РІВНЯНЬ
Інструкція
до лабораторної роботи № 3
з курсу
" Комп’ютерні методи дослідження інформаційних процесів та систем "
для студентів спеціальності 6.1601
"Інформаційна безпека"
Затверджено
на засіданні кафедри
«Захист інформації»
Протокол № __ від __________ p.
Львів – 2007
Ітераційні методи розв’язування систем лінійних алгебраїчних рівнянь: Інструкція до лабораторної роботи №3 з курсу " Комп’ютерні методи дослідження інформаційних процесів та систем" для студентів спеціальності 6.1601 "Інформаційна безпека " / Укл.: Л.В.Мороз, З.М.Стрілецький, В.М. Іванюк - Львів: НУЛП, 2007.- 12 с.
Укладачі: Леонід Васильович Мороз, к.т.н., доц.
Зеновій Михайлович Стрілецький, к.т.н., доц.
Віталій Миколайович Іванюк, асистент
Відповідальний за випуск: І.Я. Тишик, ст.викл.
Рецензент: В.В.Хома, д.т.н., проф..
В.М.Максимович, к.т.н., доц.
Мета роботи – ознайомлення з ітераційними методами розв’язування систем лінійних алгебраїчних рівнянь.
Ітераційні методи розв’язування систем лінійних
алгебраїчних рівнянь EMBED Equation.3
До ітераційних методів належать: метод простої ітерації, метод Зейделя, метод верхньої релаксації та інші.
Метод простої ітерації.
Нехай дано лінійну систему
EMBED Equation.3 (1)
Розглянемо матриці
EMBED Equation.3 EMBED Equation.3 EMBED Equation.3
Тоді систему (1) можна записати у вигляді матричного рівняння
EMBED Equation.3 (2)
Будемо вважати, що діагональні коефіцієнти EMBED Equation.3 (і = 1, 2,…, n).
Розв’яжемо перше рівняння системи (1) відносно EMBED Equation.3 , друге відносно EMBED Equation.3 і т.д. Тоді одержимо еквівалентну систему
EMBED Equation.3 (3)
де EMBED Equation.3 EMBED Equation.3 , при EMBED Equation.3 ; EMBED Equation.3 , при EMBED Equation.3 ;
EMBED Equation.3 ; EMBED Equation.3 ; EMBED Equation.3
Іноді кажуть, що система (3) зведена до нормального вигляду.
Введемо матриці та
EMBED Equation.3 EMBED Equation.3
Систему (3) запишемо у вигляді
EMBED Equation.3 (4)
Систему (3) будемо розв’язувати методом послідовних наближень. За нульове наближення позначимо, наприклад, стовпчик вільних членів EMBED Equation.3 . Далі послідовно будуємо матриці-стовпці:
EMBED Equation.3 – перше наближення
EMBED Equation.3 – друге наближення і т.д.
Будь-яке (k + 1)-е наближення обчислюється за формулою:
EMBED Equation.3 , (k = 0, 1, 2, …) (5)
В розгорнутому вигляді EMBED Equation.3 .
Якщо послідовність наближень EMBED Equation.3 має границю
EMBED Equation.3 , (6)
то ця границя є розв’язком системи (3).
На практиці ітераційний процес припиняють, коли EMBED Equation.3 , де – гранична абсолютна похибка.
Приклад. Розв’язати систему методом простої ітерації:
EMBED Equation.3 .
Зведемо систему до нормального вигляду
EMBED Equation.3 (7)
або в матричній формі
EMBED Equation.3 (8)
За нульові наближення коренів системи приймаємо
EMBED Equation.3 .
Підставляємо ці значення в праві частини рівняння (7). Одержимо перші наближення коренів
EMBED Equation.3
Далі знаходимо другі і треті наближення коренів
EMBED Equation.3
EMBED Equation.3
Умови збіжності ітераційного процесу
Нехай задано зведена до нормального вигляду система лінійних рівнянь
EMBED Equation.3
Умова збіжності: якщо сума модулів елементів рядків або модулів елементів стовпців матриці α менша ніж 1, то процес ітерації для даної системи збігається до єдиного розв’язку незалежно від вибору вектора початкових наближень.
Для системи
EMBED Equation.3
або EMBED Equation.3 ,
де EMBED Equation.3 – сума модулів по стовпцях
EMBED Equation.3
Аналогіч...
